package com.kevin.Code.Backtrack;

import java.util.ArrayList;

/**
 * @author Vinlee Xiao
 * @Classname SudokuSolver
 * @Description Leetcode 37 解数独 难度 困难 回溯算法  总体思路为回溯框架  核心如何去控制遍历
 * @Date 2021/9/27 17:12
 * @Version 1.0
 */
public class SudokuSolver {
    ArrayList<int[]> list = new ArrayList<>();
    //控制是否达到全部填充
    boolean isValid = true;
    //控制每一行的数
    boolean[][] rows = new boolean[9][9];
    boolean[][] columns = new boolean[9][9];
    boolean[][][] area = new boolean[9][9][9];

    /**
     * @param board
     */
    public void solveSudoku(char[][] board) {

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {

                if (board[i][j] == '.') {
                    list.add(new int[]{i, j});
                } else {
                    //得到该位置出现的数字 减一
                    int digit = board[i][j] - '0' - 1;
                    //将 行 列 块 全部为true
                    rows[i][digit] = true;
                    columns[j][digit] = true;
                    //属于哪一个块
                    area[i / 3][j / 3][digit] = true;
                }
            }

        }
        backtrack(board, 0);

    }

    /**
     * @param board
     * @param position 用于控制是否达到最终的填充
     */
    public void backtrack(char[][] board, int position) {

        //递归结束的条件
        if (position == list.size()) {
            isValid = false;
            return;
        }

        int[] index = list.get(position);
        int row = index[0];
        int col = index[1];

        //填充各个数字
        for (int i = 0; i < 9; i++) {

            //该数没有出现 则可以填充
            if (!rows[row][i] && !columns[col][i] && !area[row / 3][col / 3][i] && isValid) {

                board[row][col] = (char) (i + '0' + 1);
                rows[row][i] = true;
                columns[col][i] = true;
                area[row / 3][col / 3][i] = true;
                backtrack(board, position + 1);
                rows[row][i] = false;
                columns[col][i] = false;
                area[row / 3][col / 3][i] = false;

            }
        }

    }
}
